/**
 * 版权所有 (C), 2019-2019, XXX有限公司
 * 项目名：com.company.study.dsa.queue
 * 文件名: PriorityQueue
 * 日期: 2019/6/18 12:30
 * 说明:
 */
package com.company.study.dsa.queue;

/**
 * 优先级队列
 *
 * @author Anbang713
 * @create 2019/6/18
 */
public class PriorityQueue {
    private int[] array;
    private int maxSize;
    private int itemSize;

    public PriorityQueue(int maxSize) {
        this.maxSize = maxSize;
        array = new int[this.maxSize];
        itemSize = 0;
    }

    //插入数据
    public void insert(int value) {
        int j;
        if (itemSize == 0) {
            array[itemSize++] = value;
        } else {
            j = itemSize - 1;
            //选择的排序方法是插入排序，按照从大到小的顺序排列，越小的越在队列的顶端
            while (j >= 0 && value > array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = value;
            itemSize++;
        }
    }

    //移除数据,由于是按照大小排序的，所以移除数据我们指针向下移动
    //被移除的地方由于是int类型的，不能设置为null，这里的做法是设置为 -1
    public int remove() {
        int k = itemSize - 1;
        int value = array[k];
        array[k] = -1;//-1表示这个位置的数据被移除了
        itemSize--;
        return value;
    }

    //查看优先级最高的元素
    public int peekMin() {
        return array[itemSize - 1];
    }

    //判断是否为空
    public boolean isEmpty() {
        return itemSize == 0;
    }

    //判断是否满了
    public boolean isFull() {
        return itemSize == maxSize;
    }
}